//给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。 
//
// 返回执行此操作后，grid 中最大的岛屿面积是多少？ 
//
// 岛屿 由一组上、下、左、右四个方向相连的 1 形成。 
//
// 
//
// 示例 1: 
//
// 
//输入: grid = [[1, 0], [0, 1]]
//输出: 3
//解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。
// 
//
// 示例 2: 
//
// 
//输入: grid = [[1, 1], [1, 0]]
//输出: 4
//解释: 将一格0变成1，岛屿的面积扩大为 4。 
//
// 示例 3: 
//
// 
//输入: grid = [[1, 1], [1, 1]]
//输出: 4
//解释: 没有0可以让我们变成1，面积依然为 4。 
//
// 
//
// 提示： 
//
// 
// n == grid.length 
// n == grid[i].length 
// 1 <= n <= 500 
// grid[i][j] 为 0 或 1 
// 
//
// Related Topics 深度优先搜索 广度优先搜索 并查集 数组 矩阵 👍 353 👎 0


package LeetCode.editor.cn;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author ldltd
 * @date 2023-08-25 20:13:45
 * @description 827.最大人工岛
 */
public class MakingALargeIsland{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new MakingALargeIsland().new Solution();
		int[][] grid={{1,1},{0,1}};
		 System.out.println(solution.largestIsland(grid));
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int largestIsland(int[][] grid) {
		int res=0,t=2;
		Map<Integer, Integer> map = new HashMap<>();
		//先对每个岛屿进行标注，用t给他们标号属于哪个岛屿，并把面积赋值到map中
		for (int i = 0; i < grid.length; i++) {
			for (int j = 0; j < grid[0].length; j++) {
				if(grid[i][j]==1){
					int a=dfs(grid,i,j,t);
					//预防后面找海洋的时候没有
					res=Math.max(res,a);
					map.put(t,a);
					t++;
				}
			}
		}
		//找最大的一个格子
		int[] dx={1,-1,0,0};
		int [] dy={0,0,-1,1};
		//用来保存已经访问的岛
		Set<Integer> set=new HashSet<>();
		for (int i = 0; i < grid.length; i++) {
			for (int j = 0; j < grid[0].length; j++) {
				t=1;
				set.clear();
				//找到一块海洋
				if(grid[i][j]==0){
					for (int k = 0; k < 4; k++) {
						int x=i+dx[k];
						int y=j+dy[k];
						//如果位置合法，就加上对应岛屿的面积
						if(inArea(grid,x,y)&&grid[x][y]!=0){
							if(!set.contains(grid[x][y])){
								t+=map.get(grid[x][y]).intValue();

							}
								set.add(grid[x][y]);

						}
					}
				}
				res=Math.max(res,t);
			}
		}
		return  res;
	}
	private  int dfs(int[][] grid,int i,int j,int t){
		//超出范围或者不是陆地的时候就走
			if(!inArea(grid,i,j)||grid[i][j]!=1) return 0;
			grid[i][j]=t;
			return 1+dfs(grid,i+1,j,t)
					+dfs(grid,i-1,j,t)
					+dfs(grid,i,j+1,t)
					+dfs(grid,i,j-1,t);
	}
	//判断不越界
	private boolean inArea(int [][]grid,int i,int j){
		if(i<0||i>=grid.length||j<0||j>=grid[0].length)
			return false;
		return true;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
